﻿using System;
using System.Collections.Generic;
using System.Linq;
using Algoritmia.DataStructures.Lists;
using Algoritmia.Utils;

namespace Algoritmia.Problems.Arithmetics
{
    public class BigIntBase
    {
        protected readonly DataStructures.Lists.IList<int> _digit;

        public BigIntBase(IEnumerable<int> digits)
        {
            _digit = digits.Reverse().ToAlgoritmiaList();
        }

        public BigIntBase(string digits)
        {
            _digit = AlgoritmiaFactory.Lists<int>.Default;
            for (var i = digits.Length - 1; i >= 0; i--)
            {
                _digit.Add(int.Parse(digits.Substring(i, 1)));
            }
        }

        public BigIntBase(int number)
        {
            _digit = AlgoritmiaFactory.Lists<int>.Default;
            while (number > 0)
            {
                _digit.Add(number % 10);
                number /= 10;
            }
            if (_digit.Count == 0)
            {
                _digit.Add(0);
            }
        }

        public BigIntBase(long number)
        {
            _digit = AlgoritmiaFactory.Lists<int>.Default;
            while (number > 0)
            {
                _digit.Add((int)(number % 10));
                number /= 10;
            }
            if (_digit.Count == 0)
            {
                _digit.Add(0);
            }
        }

        public int this[int index]
        {
            get
            {
                if (index >= 0 && index < _digit.Count)
                    return _digit[index];
                return 0;
            }
        }

        public int Count
        {
            get
            {
                int i;
                for (i = _digit.Count - 1; i >= 0; i--)
                {
                    if (_digit[i] != 0) break;
                }
                return i + 1;
            }
        }

        public override string ToString()
        {
            for (int i = _digit.Count - 1; i >= 0; i--)
            {
                if (_digit[i] != 0)
                    break;
            }
            return string.Join("", _digit.Where((e, i) => i < i + 1).Reverse());
        }

        public BigIntBase Add(BigIntBase other)
        {
            var n = Math.Max(this.Count, other.Count);
            var result = AlgoritmiaFactory.Lists<int>.Default;
            int carry = 0;
            for (int i = 0; i < n; i++)
            {
                var s = this[i] + other[i] + carry;
                carry = s / 10;
                result.Add(s % 10);
            }
            if (carry != 0)
            {
                result.Add(carry);
            }
            return new BigIntBase(result.Reverse().ToAlgoritmiaList());
        }

        public BigIntBase LeftShift(int n)
        {
            return new BigIntBase(_digit.Reverse().Concat(Enumerable.Repeat(0, n)).ToAlgoritmiaList());
        }

        public BigIntBase Multiply(BigIntBase other)
        {
            var n = Math.Max(this.Count, other.Count);
            if (n <= 1)
            {
                var r = this[0]*other[0];
                if ( r < 10)
                {
                    return new BigIntBase(r);
                }
                return new BigIntBase(new ArrayList<int> { r/10 , r%10});
            }
            var limit = n / 2;
            var w = new BigIntBase(this._digit.Where((e, i) => i >= limit).Reverse().ToAlgoritmiaList());
            var x = new BigIntBase(this._digit.Where((e, i) => i < limit).Reverse().ToAlgoritmiaList());
            var y = new BigIntBase(other._digit.Where((e, i) => i >= limit).Reverse().ToAlgoritmiaList());
            var z = new BigIntBase(other._digit.Where((e, i) => i < limit).Reverse().ToAlgoritmiaList());
            return ((w*y) << (limit << 1)) + (((w*z) + x*y) << limit) + x*z;
        }

        public static BigIntBase operator +(BigIntBase a, BigIntBase b)
        {
            return a.Add(b);
        }

        public static BigIntBase operator <<(BigIntBase a, int n)
        {
            return a.LeftShift(n);
        }

        public static BigIntBase operator *(BigIntBase a, BigIntBase b)
        {
            return a.Multiply(b);
        }
    }

    public class BigInt : BigIntBase
    {

        public BigInt(IEnumerable<int> digits)
            : base(digits)
        {
        }

        public BigInt(string digits)
            : base(digits)
        {
        }

        public BigInt(int number)
            : base(number)
        {
        }

        public BigInt(long number)
            : base(number)
        {
        }

        public BigInt Add(BigInt other)
        {
            var r = base.Add(other);
            return new BigInt(r.ToString());
        }

        public new BigInt LeftShift(int n)
        {
            var r = base.LeftShift(n);
            return new BigInt(r.ToString());
        }

        public BigInt Substract(BigInt other)
        {
            int n = Math.Max(other.Count, Count);
            var result = AlgoritmiaFactory.Lists<int>.Default;
            var carry = 0;
            for (int i = 0; i < n; i++)
            {
                var s = this[i] - other[i] + carry;
                if (s < 0)
                {
                    carry = -1;
                    result.Add(10 + s);
                }
                else
                {
                    carry = 0;
                    result.Add(s % 10);
                }
            }
            if (carry != 0)
            {
                result.Add(-carry);
            }
            return new BigInt(result.Reverse().ToAlgoritmiaList());
        }

        public BigInt Multiply(BigInt other)
        {
            int n = Math.Max(Count, other.Count);
            if ( n <= 1)
            {
                var r = this[0] * other[0];
                if (r < 10)
                {
                    return new BigInt(r);
                }
                var list = AlgoritmiaFactory.Lists<int>.Default;
                list.Add(r / 10);
                list.Add(r % 10);
                return new BigInt(list);
            }
            else
            {
                var limit = n/2;
                var w = new BigInt(this._digit.Where((e, i) => i >= limit).Reverse().ToAlgoritmiaList());
                var x = new BigInt(this._digit.Where((e, i) => i < limit).Reverse().ToAlgoritmiaList());
                var y = new BigInt(other._digit.Where((e, i) => i >= limit).Reverse().ToAlgoritmiaList());
                var z = new BigInt(other._digit.Where((e, i) => i < limit).Reverse().ToAlgoritmiaList());
                var alpha = w * y;
                var beta = x * z;
                var gamma = (w + x)*(y + z);
                return (alpha << (limit << 1)) + ((gamma - beta - alpha) << limit) + beta;

            }
        }

        public static BigInt operator +(BigInt a, BigInt b)
        {
            return a.Add(b);
        }

        public static BigInt operator <<(BigInt a, int n)
        {
            return a.LeftShift(n);
        }

        public static BigInt operator -(BigInt a, BigInt b)
        {
            return a.Substract(b);
        }

        public static BigInt operator *(BigInt a, BigInt b)
        {
            return a.Multiply(b);
        }
    }
}